<!DOCTYPE html>


<html lang="zh-CN">


<head>
  <meta charset="utf-8" />
  <meta name="baidu-site-verification" content="code-kg5UjKJZM2" />
   
  <meta name="keywords" content="活,炼" />
   
  <meta name="description" content="shimmerjordan" />
  
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
  <title>
    八大排序算法笔记 |  丛烨-shimmerjordan
  </title>
  <meta name="generator" content="hexo-theme-ayer">
  
  <link rel="shortcut icon" href="/favicon.ico" />
  
  
<link rel="stylesheet" href="/dist/main.css">

  <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Shen-Yu/cdn/css/remixicon.min.css">
  
<link rel="stylesheet" href="/css/custom.css">

  
  <script src="https://cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>
  
  

<script type="text/javascript">
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');

ga('create', 'G-Q0DT8B8VJW', 'auto');
ga('send', 'pageview');

</script>



  
<script>
var _hmt = _hmt || [];
(function() {
	var hm = document.createElement("script");
	hm.src = "https://hm.baidu.com/hm.js?6d06f826e125297d4ce0fa7a1449328e";
	var s = document.getElementsByTagName("script")[0]; 
	s.parentNode.insertBefore(hm, s);
})();
</script>


<link rel="alternate" href="/atom.xml" title="丛烨-shimmerjordan" type="application/atom+xml">
</head>

</html>

	<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/font-awesome/css/font-awesome.min.css">
	<script src="https://cdn.jsdelivr.net/gh/stevenjoezhang/live2d-widget@latest/autoload.js"></script>


<body>
  <div id="app">
    
      
    <main class="content on">
      <section class="outer">
  <article
  id="post-Sorting-Algorithms"
  class="article article-type-post"
  itemscope
  itemprop="blogPost"
  data-scroll-reveal
>
  <div class="article-inner">
    
    <header class="article-header">
       
<h1 class="article-title sea-center" style="border-left:0" itemprop="name">
  八大排序算法笔记
</h1>
 

    </header>
     
    <div class="article-meta">
      <a href="/2022/02/25/8SortingAlgorithms/" class="article-date">
  <time datetime="2022-02-25T03:16:10.000Z" itemprop="datePublished">2022-02-25</time>
</a> 
  <div class="article-category">
    <a class="article-category-link" href="/categories/Algorithm/">Algorithm</a>
  </div>
  
<div class="word_count">
    <span class="post-time">
        <span class="post-meta-item-icon">
            <i class="ri-quill-pen-line"></i>
            <span class="post-meta-item-text"> 字数统计:</span>
            <span class="post-count">2.6k</span>
        </span>
    </span>

    <span class="post-time">
        &nbsp; | &nbsp;
        <span class="post-meta-item-icon">
            <i class="ri-book-open-line"></i>
            <span class="post-meta-item-text"> 阅读时长≈</span>
            <span class="post-count">10 分钟</span>
        </span>
    </span>
</div>
 
    </div>
      
    <div class="tocbot"></div>




  
    <div class="article-entry" itemprop="articleBody">
       
  <h1 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h1><p>排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。这里介绍的是内部排序中的八大主流排序算法：</p>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/8SortingAlg/1.jpg" width='70%'>
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">算法结构</div>
</center>

<p>当$n$较大，则应采用时间复杂度为$O(nlog2n)$的排序方法：快速排序、堆排序或归并排序序。其中快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的<strong>平均</strong>时间最短<strong>但不稳定</strong>。</p>
<span id="more"></span>
<h1 id="插入排序—直接插入排序"><a href="#插入排序—直接插入排序" class="headerlink" title="插入排序—直接插入排序"></a><a id="insertSort">插入排序—直接插入排序</a></h1><p>Note：设立一个作为临时存储和判断数组边界的哨兵。</p>
<p><strong>基本思想</strong></p>
<p>将一个记录插入到已排序好的有序表中，从而得到一个有序子表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止（$n-1$次操作）。</p>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/8SortingAlg/2.jpg" width='50%'>
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">直接插入排序</div>
</center>

<p>Tip：如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，<strong>所以插入排序是稳定的。</strong></p>
<p><strong>算法实现</strong></p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">insertSort</span>(<span class="params">target</span>):</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>, <span class="built_in">len</span>(target)):</span><br><span class="line">        <span class="keyword">if</span> target[i] &lt; target[i-<span class="number">1</span>]:     <span class="comment"># 若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入</span></span><br><span class="line">            temp = target[i]            <span class="comment"># 复制为哨兵，即存储待排序元素</span></span><br><span class="line">            target[i] = target[i-<span class="number">1</span>]</span><br><span class="line">            j = i - <span class="number">1</span></span><br><span class="line">            <span class="keyword">while</span> temp &lt; target[j]:     <span class="comment"># 查找在有序表的插入位置</span></span><br><span class="line">                target[j+<span class="number">1</span>] = target[j]</span><br><span class="line">                j -= <span class="number">1</span>                  <span class="comment"># 元素后移</span></span><br><span class="line">                <span class="keyword">if</span> j &lt; <span class="number">0</span>: <span class="keyword">break</span></span><br><span class="line">            target[j+<span class="number">1</span>] = temp          <span class="comment"># 插入到正确位置</span></span><br><span class="line">    <span class="keyword">return</span> target</span><br><span class="line"></span><br><span class="line">target = [<span class="number">3</span>,<span class="number">1</span>,<span class="number">5</span>,<span class="number">7</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">6</span>]</span><br><span class="line"><span class="built_in">print</span>(insertSort(target))</span><br></pre></td></tr></table></figure>
<p>时间复杂度为$O(n^2)$，其它的插入排序有二分插入排序，2-路插入排序。</p>
<h1 id="插入排序—希尔排序"><a href="#插入排序—希尔排序" class="headerlink" title="插入排序—希尔排序"></a>插入排序—希尔排序</h1><p>1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进，又称<strong>缩小增量排序</strong></p>
<p><strong>基本思想</strong></p>
<p>先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。</p>
<ol>
<li><p>选择一个增量序列$t_1,t_2, \dots ,t_k$，其中$t_i&gt;t_j$，$t_k=1$；</p>
</li>
<li><p>按增量序列个数$k$，对序列进行$k$趟排序；</p>
</li>
<li><p>每趟排序，根据对应的增量$t_i$，将待排序列分割成若干长度为$m$的子序列，分别对各子表进行直接插入排序。仅增量因子为$1$时，整个序列作为一个表来处理，表长度即为整个序列的长度。</p>
</li>
</ol>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/8SortingAlg/3.jpg" width='70%'>
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">希尔排序</div>
</center>

<p><strong>算法实现</strong></p>
<p>我们简单处理增量序列：增量序列$d = \{n/2,n/4,n/8, \cdots, 1\}$，$n$为要排序数的个数。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">shellInsertSort</span>(<span class="params">target, dk</span>):</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(dk, <span class="built_in">len</span>(target)):</span><br><span class="line">        <span class="keyword">if</span> target[i] &lt; target[i-dk]:</span><br><span class="line">            j = i-dk</span><br><span class="line">            temp = target[i]</span><br><span class="line">            target[i] = target[i-dk]</span><br><span class="line">            <span class="keyword">while</span> temp &lt; target[j]:</span><br><span class="line">                target[j+dk] = target[j]</span><br><span class="line">                j -= dk</span><br><span class="line">                <span class="keyword">if</span> j &lt; <span class="number">0</span>: <span class="keyword">break</span></span><br><span class="line">            target[j+dk] = temp</span><br><span class="line">    <span class="keyword">return</span> target</span><br><span class="line"></span><br><span class="line"><span class="keyword">def</span> <span class="title function_">shellSort</span>(<span class="params">target</span>):</span><br><span class="line">    dk = <span class="built_in">len</span>(target) // <span class="number">2</span></span><br><span class="line">    <span class="keyword">while</span> dk &gt;= <span class="number">1</span>:</span><br><span class="line">        shellInsertSort(target, dk)</span><br><span class="line">        dk //= <span class="number">2</span></span><br><span class="line">    <span class="keyword">return</span> target</span><br><span class="line"></span><br><span class="line">target = [<span class="number">3</span>,<span class="number">1</span>,<span class="number">5</span>,<span class="number">7</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">6</span>]</span><br><span class="line"><span class="built_in">print</span>(shellSort(target))</span><br></pre></td></tr></table></figure>
<p><strong>复杂度</strong>：希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列$d$的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除$1$外没有公因子，且最后一个增量因子必须为$1$。希尔排序方法是一个<strong>不稳定的排序方法</strong>。</p>
<h1 id="选择排序—简单选择排序"><a href="#选择排序—简单选择排序" class="headerlink" title="选择排序—简单选择排序"></a>选择排序—简单选择排序</h1><p><strong>基本思想</strong></p>
<p>在要排序的一组数中，选出最小（或者最大）的一个数与第$1$个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第$2$个位置的数交换，依次类推，直到第 $n-1$个元素（倒数第二个数）和第$n$个元素（最后一个数）比较为止。</p>
<p>第$1$趟，从$n$个记录中找出关键码最小的记录与第$1$个记录交换；</p>
<p>第$2$趟，从第$2$个记录开始的$n-1$个记录中再选出关键码最小的记录与第$2$个记录交换；</p>
<p>$\cdots$</p>
<p>第$i$趟，则从第$i$个记录开始的$n-i+1$个记录中选出关键码最小的记录与第$i$个记录交换，直到整个序列按关键码有序。<br><strong>算法实现</strong></p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">minIndex</span>(<span class="params">target, start</span>):</span><br><span class="line">    res = start </span><br><span class="line">    min_num = target[start]</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(start, <span class="built_in">len</span>(target)):</span><br><span class="line">        <span class="keyword">if</span> target[i] &lt; min_num:</span><br><span class="line">            min_num = target[i]</span><br><span class="line">            res = i</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line"></span><br><span class="line"><span class="keyword">def</span> <span class="title function_">selectSort</span>(<span class="params">target</span>):</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(target)):</span><br><span class="line">        key = minIndex(target, i)</span><br><span class="line">        <span class="keyword">if</span> key != i:</span><br><span class="line">            target[i], target[key] = target[key], target[i]</span><br><span class="line">    <span class="keyword">return</span> target</span><br><span class="line"></span><br><span class="line">target = [<span class="number">3</span>,<span class="number">1</span>,<span class="number">5</span>,<span class="number">7</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">6</span>]</span><br><span class="line"><span class="built_in">print</span>(selectSort(target))</span><br></pre></td></tr></table></figure>
<p><strong>简单选择排序的改进——二元选择排序</strong></p>
<p>简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对$n$个数据进行排序，最多只需进行$[n/2]$趟循环即可。具体实现不再赘述。</p>
<h1 id="选择排序—堆排序"><a href="#选择排序—堆排序" class="headerlink" title="选择排序—堆排序"></a>选择排序—堆排序</h1><p>堆排序是一种树形选择排序，是对直接选择排序的有效改进。<code>python</code>内部实现了最小堆<a target="_blank" rel="noopener" href="https://docs.python.org/zh-cn/3/library/heapq.html">heapq优先队列</a></p>
<p><strong>基本思想</strong></p>
<p>初始时把要排序的$n$个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到$n$个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面$n-1$个元素重新调整使之成为堆，输出堆顶元素，得到$n$个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有$n$个节点的有序序列。称这个过程为<strong>堆排序</strong>。<br>因此，实现堆排序需解决两个问题：  </p>
<ol>
<li>如何将$n$个待排序的数建成堆；  </li>
<li>输出堆顶元素后，怎样调整剩余$n-1$个元素，使其成为一个新堆。</li>
</ol>
<p>首先讨论第二个问题：输出堆顶元素后，对剩余$n-1$元素重新建成堆的调整过程。<br><strong>调整小顶堆的方法：</strong></p>
<p>1) 设有$m$个元素的堆，输出堆顶元素后，剩下$m-1$个元素。将堆底元素送入堆顶（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。</p>
<p>2) 将根结点与左、右子树中较小元素的进行交换。</p>
<p>3) 若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法<code>2</code>.</p>
<p>4) 若与右子树交换：如果右子树堆被破坏，即右子树的根结点不 满足堆的性质。则重复方法<code>2</code>.</p>
<p>5) 继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。</p>
<p>再讨论对$n$个元素初始建堆的过程。</p>
<p><strong>建堆方法：</strong> 对初始序列建堆的过程，就是一个反复进行筛选的过程。</p>
<ol>
<li><p>$n$个结点的完全二叉树，则最后一个结点是第$[n/2]$个结点的子树。</p>
</li>
<li><p>筛选从第$[n/2]$个结点为根的子树开始，该子树成为堆。</p>
</li>
<li><p>之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。</p>
</li>
</ol>
<p><strong>算法的实现：</strong></p>
<p>从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 构造最小堆 </span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">MinHeap</span>():</span><br><span class="line">    <span class="keyword">def</span> <span class="title function_">__init__</span>(<span class="params">self, maxSize=<span class="literal">None</span></span>):</span><br><span class="line">        self.maxSize = maxSize </span><br><span class="line">        self.array = [<span class="literal">None</span>] * maxSize </span><br><span class="line">        self._count = <span class="number">0</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">def</span> <span class="title function_">length</span>(<span class="params">self</span>):</span><br><span class="line">        <span class="keyword">return</span> self._count </span><br><span class="line"></span><br><span class="line">    <span class="keyword">def</span> <span class="title function_">show</span>(<span class="params">self</span>):</span><br><span class="line">        <span class="keyword">if</span> self._count &lt;= <span class="number">0</span>:</span><br><span class="line">            <span class="built_in">print</span>(<span class="string">&#x27;null&#x27;</span>)</span><br><span class="line">        <span class="built_in">print</span>(self.array[: self._count], end=<span class="string">&#x27;, &#x27;</span>)</span><br><span class="line"></span><br><span class="line">    <span class="keyword">def</span> <span class="title function_">add</span>(<span class="params">self, value</span>):</span><br><span class="line">        <span class="comment"># 增加元素</span></span><br><span class="line">        <span class="keyword">if</span> self._count &gt;= self.maxSize:</span><br><span class="line">            <span class="keyword">raise</span> Exception(<span class="string">&#x27;The array is Full&#x27;</span>)</span><br><span class="line">        self.array[self._count] = value</span><br><span class="line">        self._shift_up(self._count)</span><br><span class="line">        self._count += <span class="number">1</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">def</span> <span class="title function_">_shift_up</span>(<span class="params">self, index</span>):</span><br><span class="line">        <span class="comment"># 比较结点与根节点的大小， 较小的为根结点</span></span><br><span class="line">        <span class="keyword">if</span> index &gt; <span class="number">0</span>:</span><br><span class="line">            parent = (index - <span class="number">1</span>) // <span class="number">2</span></span><br><span class="line">            <span class="keyword">if</span> self.array[parent] &gt; self.array[index]:</span><br><span class="line">                self.array[parent], self.array[index] = self.array[index], self.array[parent]</span><br><span class="line">                self._shift_up(parent)</span><br><span class="line"></span><br><span class="line">    <span class="keyword">def</span> <span class="title function_">extract</span>(<span class="params">self</span>):           </span><br><span class="line">        <span class="comment"># 获取最小值，并更新数组</span></span><br><span class="line">        <span class="keyword">if</span> self._count &lt;= <span class="number">0</span>:</span><br><span class="line">            <span class="keyword">raise</span> Exception(<span class="string">&#x27;The array is Empty&#x27;</span>)</span><br><span class="line">        value = self.array[<span class="number">0</span>]</span><br><span class="line">        self._count -= <span class="number">1</span> <span class="comment"># 更新数组的长度</span></span><br><span class="line">        self.array[<span class="number">0</span>] = self.array[self._count] <span class="comment"># 将最后一个结点放在前面</span></span><br><span class="line">        self._shift_down(<span class="number">0</span>)</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> value </span><br><span class="line"></span><br><span class="line">    <span class="keyword">def</span> <span class="title function_">_shift_down</span>(<span class="params">self, index</span>):  </span><br><span class="line">        <span class="comment"># 此时index 是根结点</span></span><br><span class="line">        <span class="keyword">if</span> index &lt; self._count:</span><br><span class="line">            left = <span class="number">2</span> * index + <span class="number">1</span></span><br><span class="line">            right = <span class="number">2</span> * index + <span class="number">2</span></span><br><span class="line">            <span class="comment"># 判断左右结点是否越界，是否小于根结点，如果是就交换</span></span><br><span class="line">            <span class="keyword">if</span> left &lt; self._count <span class="keyword">and</span> right &lt; self._count <span class="keyword">and</span> self.array[left] &lt; self.array[index] <span class="keyword">and</span> self.array[left] &lt; self.array[right]:</span><br><span class="line">                self.array[index], self.array[left] = self.array[left], self.array[index] <span class="comment">#交换得到较小的值</span></span><br><span class="line">                self._shift_down(left)</span><br><span class="line">            <span class="keyword">elif</span> left &lt; self._count <span class="keyword">and</span> right &lt; self._count <span class="keyword">and</span> self.array[right] &lt; self.array[left] <span class="keyword">and</span> self.array[right] &lt; self.array[index]:</span><br><span class="line">                self.array[right], self.array[index] = self.array[index], self.array[right]</span><br><span class="line">                self._shift_down(right)</span><br><span class="line"></span><br><span class="line">            <span class="comment"># 特殊情况： 如果只有做叶子结点</span></span><br><span class="line">            <span class="keyword">if</span> left &lt; self._count <span class="keyword">and</span> right &gt; self._count <span class="keyword">and</span> self.array[left] &lt; self.array[index]:</span><br><span class="line">                self.array[left], self.array[index] = self.array[index], self.array[left]</span><br><span class="line">                self._shift_down(left)</span><br><span class="line"></span><br><span class="line">mi = MinHeap(<span class="number">10</span>)</span><br><span class="line">num = [<span class="number">3</span>,<span class="number">1</span>,<span class="number">5</span>,<span class="number">7</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">6</span>,<span class="number">10</span>,<span class="number">8</span>]</span><br><span class="line"><span class="built_in">print</span>(<span class="string">&#x27;---------小顶堆----------&#x27;</span>)</span><br><span class="line"><span class="keyword">for</span> i <span class="keyword">in</span> num:</span><br><span class="line">    mi.add(i)</span><br><span class="line">res = []</span><br><span class="line"><span class="keyword">for</span> _ <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(num)):</span><br><span class="line">    res.append(mi.extract())</span><br><span class="line"><span class="built_in">print</span>(res)</span><br></pre></td></tr></table></figure>
<p><strong>复杂度：</strong></p>
<p>设树深度为$k=[log_2n]+1$，从根到叶的筛选，元素比较次数至多$2(k-1)$次，交换记录至多$k$次。所以，在建好堆后，排序过程中的筛选次数不超过:</p>
<script type="math/tex; mode=display">
2(\lfloor log_2(n-1)\rfloor+\lfloor log_2(n-2)\rfloor+,\cdots,+\lfloor log_22\rfloor)<2n(\lfloor log_2n\rfloor)</script><p>而建堆时的比较次数不超过$4n$次，因此堆排序最坏情况下，时间复杂度也为：$O(nlogn )$</p>
<h1 id="交换排序—冒泡排序"><a href="#交换排序—冒泡排序" class="headerlink" title="交换排序—冒泡排序"></a>交换排序—冒泡排序</h1><p><strong>基本思想：</strong></p>
<p>在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。</p>
<p><strong>算法的实现：</strong></p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">bubbleSort</span>(<span class="params">target</span>):</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(target)):</span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(target)-i-<span class="number">1</span>):</span><br><span class="line">            <span class="keyword">if</span> target[j] &gt; target[j+<span class="number">1</span>]:</span><br><span class="line">                target[j], target[j+<span class="number">1</span>] = target[j+<span class="number">1</span>], target[j]</span><br><span class="line">    <span class="keyword">return</span> target  </span><br><span class="line">target = [<span class="number">3</span>,<span class="number">1</span>,<span class="number">5</span>,<span class="number">7</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">6</span>,<span class="number">10</span>,<span class="number">8</span>]</span><br><span class="line"><span class="built_in">print</span>(bubbleSort(target))</span><br></pre></td></tr></table></figure>
<p><strong>冒泡排序算法的改进:</strong></p>
<p>对冒泡排序常见的改进方法是加入一标志性变量<code>exchange</code>，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。本文再提供以下两种改进算法：</p>
<p>1．设置一标志性变量<code>pos</code>,用于记录每趟排序中最后一次进行交换的位置。由于<code>pos</code>位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到<code>pos</code>位置即可。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">bubbleSort_1</span>(<span class="params">target</span>):</span><br><span class="line">    i = <span class="built_in">len</span>(target) - <span class="number">1</span></span><br><span class="line">    <span class="keyword">while</span> i &gt; <span class="number">0</span>:</span><br><span class="line">        pos = <span class="number">0</span>         <span class="comment"># 每趟开始前，无记录交换</span></span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(i):</span><br><span class="line">            <span class="keyword">if</span> target[j] &gt; target[j+<span class="number">1</span>]:</span><br><span class="line">                pos = j</span><br><span class="line">                target[j], target[j+<span class="number">1</span>] = target[j+<span class="number">1</span>], target[j]</span><br><span class="line">        i = pos</span><br><span class="line">    <span class="keyword">return</span> target</span><br></pre></td></tr></table></figure>
<p>2．传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">bubbleSort_2</span>(<span class="params">target</span>):</span><br><span class="line">    low, high = <span class="number">0</span>, <span class="built_in">len</span>(target) - <span class="number">1</span></span><br><span class="line">    <span class="keyword">while</span> low &lt; high:</span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(low, high):        <span class="comment"># 正向冒泡寻找最大</span></span><br><span class="line">            <span class="keyword">if</span> target[j] &gt; target[j+<span class="number">1</span>]:</span><br><span class="line">                target[j], target[j+<span class="number">1</span>] = target[j+<span class="number">1</span>], target[j]</span><br><span class="line">        high -= <span class="number">1</span></span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(high, low, -<span class="number">1</span>):    <span class="comment"># 反向冒泡寻找最小</span></span><br><span class="line">            <span class="keyword">if</span> target[j] &lt; target[j-<span class="number">1</span>]:</span><br><span class="line">                target[j], target[j-<span class="number">1</span>] = target[j-<span class="number">1</span>], target[j]</span><br><span class="line">        low += <span class="number">1</span></span><br><span class="line">    <span class="keyword">return</span> target</span><br></pre></td></tr></table></figure>
<h1 id="交换排序—快速排序"><a href="#交换排序—快速排序" class="headerlink" title="交换排序—快速排序"></a>交换排序—快速排序</h1><p><strong>基本思想：</strong></p>
<ol>
<li><p>选择一个基准元素,通常选择第一个元素或者最后一个元素；</p>
</li>
<li><p>通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大；</p>
</li>
<li><p>此时基准元素在其排好序后的正确位置；</p>
</li>
<li><p>然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。</p>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/8SortingAlg/1.gif">
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">快速排序</div>
</center>

</li>
</ol>
<p><strong>算法实现：</strong></p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">partition</span>(<span class="params">target, low, high</span>):</span><br><span class="line">    privot = target[low]</span><br><span class="line">    <span class="keyword">while</span> low &lt; high:</span><br><span class="line">        <span class="keyword">while</span> low &lt; high <span class="keyword">and</span> target[high] &gt;= privot:</span><br><span class="line">            high -= <span class="number">1</span></span><br><span class="line">        target[low], target[high] = target[high], target[low]</span><br><span class="line">        <span class="keyword">while</span> low &lt; high <span class="keyword">and</span> target[low] &lt;= privot:</span><br><span class="line">            low += <span class="number">1</span></span><br><span class="line">        target[low], target[high] = target[high], target[low]</span><br><span class="line">    <span class="keyword">return</span> low</span><br><span class="line"></span><br><span class="line"><span class="keyword">def</span> <span class="title function_">quickSort</span>(<span class="params">target, low, high</span>):</span><br><span class="line">    <span class="keyword">if</span> low &lt; high:</span><br><span class="line">        privotLoc = partition(target, low, high)</span><br><span class="line">        quickSort(target, low, privotLoc-<span class="number">1</span>)</span><br><span class="line">        quickSort(target, privotLoc+<span class="number">1</span>, high)</span><br><span class="line">    <span class="keyword">return</span> target</span><br><span class="line"></span><br><span class="line">target = [<span class="number">3</span>,<span class="number">1</span>,<span class="number">5</span>,<span class="number">7</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">6</span>,<span class="number">10</span>,<span class="number">8</span>]</span><br><span class="line"><span class="built_in">print</span>(quickSort(target,<span class="number">0</span>,<span class="built_in">len</span>(target)-<span class="number">1</span>))</span><br></pre></td></tr></table></figure>
<p><strong>分析：</strong></p>
<p>快速排序是通常被认为在同数量级$O(nlog2n)$的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个<strong>不稳定</strong>的排序方法。</p>
<p><strong>快速排序的改进：</strong></p>
<p>在本改进算法中，只对长度大于$k$的子序列递归调用快速排序，让原序列基本有序，然后再对整个基本有序序列用<a href="#insertSort">插入排序算法</a>排序：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">quickSort_improve</span>(<span class="params">target, low, high, k</span>):</span><br><span class="line">    <span class="keyword">if</span> high - low &gt; k:</span><br><span class="line">        privotLoc = partition(target, low, high)</span><br><span class="line">        quickSort_improve(target, low, privotLoc-<span class="number">1</span>, k)</span><br><span class="line">        quickSort_improve(target, privotLoc+<span class="number">1</span>, high, k)</span><br><span class="line">    <span class="keyword">return</span> target</span><br><span class="line"></span><br><span class="line"><span class="keyword">def</span> <span class="title function_">quickSort</span>(<span class="params">target, k</span>):</span><br><span class="line">    target = quickSort_improve(target, <span class="number">0</span>, <span class="built_in">len</span>(target)-<span class="number">1</span>, k)</span><br><span class="line">    <span class="keyword">return</span> insertSort(target)</span><br><span class="line"></span><br><span class="line">target = [<span class="number">3</span>,<span class="number">1</span>,<span class="number">5</span>,<span class="number">7</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">6</span>,<span class="number">10</span>,<span class="number">8</span>]</span><br><span class="line"><span class="built_in">print</span>(quickSort(target,<span class="number">8</span>))</span><br></pre></td></tr></table></figure>
<h1 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h1><p><strong>基本思想：</strong></p>
<p>归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。</p>
<p><strong>合并方法：</strong></p>
<p>设<code>r[i…n]</code>由两个有序子表<code>r[i…m]</code>和<code>r[m+1…n]</code>组成，两个子表长度分别为<code>n-i +1</code>、<code>n-m</code>。</p>
<ol>
<li><p><code>j=m+1</code>；<code>k=i</code>；<code>i=i</code>；# 置两个子表的起始下标及辅助数组的起始下标；</p>
</li>
<li><p>若<code>i&gt;m</code> 或<code>j&gt;n</code>，转⑷；# 其中一个子表已合并完，比较选取结束；</p>
</li>
<li><p># 选取<code>r[i]</code>和<code>r[j]</code>较小的存入辅助数组<code>rf</code><br>如果<code>r[i]&lt;r[j]</code>，<code>rf[k]=r[i]</code>；<code>i++</code>； <code>k++</code>； 转⑵<br>否则，<code>rf[k]=r[j]</code>；<code>j++</code>；<code>k++</code>； 转⑵</p>
</li>
<li><p># 将尚未处理完的子表中元素存入rf<br>如果<code>i&lt;=m</code>，将<code>r[i…m]</code>存入<code>rf[k…n]</code>  # 前一子表非空<br>如果<code>j&lt;=n</code> ,  将<code>r[j…n]</code> 存入<code>rf[k…n]</code> # 后一子表非空</p>
</li>
<li><p>合并结束。</p>
</li>
</ol>
<p><strong>算法实现：</strong></p>
<p>这里直接实现两路归并的迭代版本：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">merge</span>(<span class="params">a, b</span>):</span><br><span class="line">    c = []</span><br><span class="line">    h = j = <span class="number">0</span></span><br><span class="line">    <span class="keyword">while</span> j &lt; <span class="built_in">len</span>(a) <span class="keyword">and</span> h &lt; <span class="built_in">len</span>(b):</span><br><span class="line">        <span class="keyword">if</span> a[j] &lt; b[h]:</span><br><span class="line">            c.append(a[j])</span><br><span class="line">            j += <span class="number">1</span></span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            c.append(b[h])</span><br><span class="line">            h += <span class="number">1</span></span><br><span class="line">    <span class="keyword">if</span> j == <span class="built_in">len</span>(a):</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> b[h:]: c.append(i)</span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> a[j:]: c.append(i)</span><br><span class="line">    <span class="keyword">return</span> c</span><br><span class="line"></span><br><span class="line"><span class="keyword">def</span> <span class="title function_">merge_sort</span>(<span class="params">target</span>):</span><br><span class="line">    <span class="keyword">if</span> <span class="built_in">len</span>(target) &lt;= <span class="number">1</span>:</span><br><span class="line">        <span class="keyword">return</span> target</span><br><span class="line">    middle = <span class="built_in">len</span>(target) // <span class="number">2</span></span><br><span class="line">    left = merge_sort(target[:middle])</span><br><span class="line">    right = merge_sort(target[middle:])</span><br><span class="line">    <span class="keyword">return</span> merge(left, right)</span><br><span class="line"></span><br><span class="line">target = [<span class="number">3</span>,<span class="number">1</span>,<span class="number">5</span>,<span class="number">7</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">6</span>,<span class="number">10</span>,<span class="number">8</span>]</span><br><span class="line"><span class="built_in">print</span>(merge_sort(target))</span><br></pre></td></tr></table></figure>
<h1 id="桶排序-基数排序"><a href="#桶排序-基数排序" class="headerlink" title="桶排序/基数排序"></a>桶排序/基数排序</h1><p>说基数排序之前，我们先说<strong>桶排序</strong>：</p>
<p><strong>基本思想：</strong> 是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间$Θ(n)$。但桶排序并不是比较排序，他不受到$Θ(nlogn)$下限的影响。</p>
<p>简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。  </p>
<p>例如要对大小为$[1,1000]$范围内的$n$个整数<code>A[1..n]</code>排序。首先，可以把桶设为大小为<code>10</code>的范围，具体而言，设集合<code>B[1]</code>存储$[1,10]$的整数，集合<code>B[2]</code>存储 $(10,20]$的整数，……集合<code>B[i]</code>存储$((i-1) \times 10, i \times 10]$的整数，$i=1,2,..100$。总共有$100$个桶。  </p>
<p>然后，对<code>A[1..n]</code>从头到尾扫描一遍，把每个<code>A[i]</code>放入对应的桶<code>B[j]</code>中。  再对这$100$个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。</p>
<p>最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。  </p>
<p>假设有$n$个数字，有$m$个桶，如果数字是平均分布的，则每个桶里面平均有$n/m$个数字。如果对每个桶中的数字采用快速排序，那么整个算法的复杂度是  </p>
<script type="math/tex; mode=display">
O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)</script><p>$$</p>
<p>从上式看出，当$m$接近$n$的时候，桶排序复杂度接近$O(n)$。当然，以上复杂度的计算是基于输入的$n$个数字是平均分布这个假设的。这个假设是很强的  ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。  </p>
<p><strong>两种多关键码排序方法：</strong></p>
<p>多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：</p>
<p>最高位优先(Most Significant Digit first)法，简称<strong>MSD</strong>法：</p>
<ol>
<li><p>先按<code>k1</code>排序分组，将序列分成若干子序列，同一组序列的记录中，关键码<code>k1</code>相等。</p>
</li>
<li><p>再对各组按<code>k2</code>排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码<code>kd</code>对各子组排序后。</p>
</li>
<li><p>再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD法。</p>
</li>
</ol>
<p>最低位优先(Least Significant Digit first)法，简称<strong>LSD</strong>法：</p>
<p>1) 先从<code>kd</code>开始排序，再对<code>kd-1</code>进行排序，依次重复，直到按<code>k1</code>排序分组分成最小的子序列后。</p>
<p>2) 最后将各个子序列连接起来，便可得到一个有序的序列，扑克牌按花色、面值排序中介绍的方法二即是LSD法。</p>
<p><strong>基于LSD的基数排序:</strong></p>
<p>按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。</p>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/8SortingAlg/5.jpg" width='70%'>
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">基数排序</div>
</center>

<p><strong>算法实现：</strong></p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">radix_sort</span>(<span class="params">s</span>):</span><br><span class="line">    <span class="string">&quot;&quot;&quot;基数排序&quot;&quot;&quot;</span></span><br><span class="line">    i = <span class="number">0</span> <span class="comment"># 记录当前正在排拿一位，最低位为1</span></span><br><span class="line">    max_num = <span class="built_in">max</span>(s)  <span class="comment"># 最大值</span></span><br><span class="line">    j = <span class="built_in">len</span>(<span class="built_in">str</span>(max_num))  <span class="comment"># 记录最大值的位数</span></span><br><span class="line">    <span class="keyword">while</span> i &lt; j:</span><br><span class="line">        bucket_list =[[] <span class="keyword">for</span> _ <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">10</span>)] <span class="comment">#初始化桶数组</span></span><br><span class="line">        <span class="keyword">for</span> x <span class="keyword">in</span> s:</span><br><span class="line">            bucket_list[<span class="built_in">int</span>(x / (<span class="number">10</span>**i)) % <span class="number">10</span>].append(x) <span class="comment"># 找到位置放入桶数组</span></span><br><span class="line">        <span class="built_in">print</span>(bucket_list)</span><br><span class="line">        s.clear()</span><br><span class="line">        <span class="keyword">for</span> x <span class="keyword">in</span> bucket_list:   <span class="comment"># 放回原序列</span></span><br><span class="line">            <span class="keyword">for</span> y <span class="keyword">in</span> x:</span><br><span class="line">                s.append(y)</span><br><span class="line">        i += <span class="number">1</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">&#x27;__main__&#x27;</span>:</span><br><span class="line">    a = [<span class="number">334</span>,<span class="number">5</span>,<span class="number">67</span>,<span class="number">345</span>,<span class="number">7</span>,<span class="number">345345</span>,<span class="number">99</span>,<span class="number">4</span>,<span class="number">23</span>,<span class="number">78</span>,<span class="number">45</span>,<span class="number">1</span>,<span class="number">3453</span>,<span class="number">23424</span>]</span><br><span class="line">    radix_sort(a)</span><br><span class="line">    <span class="built_in">print</span>(a)</span><br></pre></td></tr></table></figure>
<h1 id="Summary"><a href="#Summary" class="headerlink" title="Summary"></a>Summary</h1><p><strong>各种排序的稳定性，时间复杂度和空间复杂度对比：</strong></p>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/8SortingAlg/6.jpg" width='70%'>
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">算法比较</div>
</center>

<p><strong>说明：</strong></p>
<ul>
<li><p>当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至$O(n)$；</p>
</li>
<li><p>而快速排序则相反，当原表基本有序时，将退化为冒泡排序，时间复杂度提高为$O(n^2)$；</p>
</li>
<li><p>原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。</p>
</li>
</ul>
<p><strong>稳定性：</strong></p>
<p>排序算法的稳定性：若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；否则不稳定。 </p>
<p>排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较；</p>
<p><strong>稳定的排序算法：</strong> 冒泡排序、插入排序、归并排序和基数排序</p>
<p><strong>非稳定的排序算法：</strong> 选择排序、快速排序、希尔排序、堆排序</p>
 
      <!-- reward -->
      
      <div id="reword-out">
        <div id="reward-btn">
          打赏
        </div>
      </div>
      
    </div>
    

    <!-- copyright -->
    
    <div class="declare">
      <ul class="post-copyright">
        <li>
          <i class="ri-copyright-line"></i>
          <strong>版权声明： </strong>
          
          本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
          
        </li>
      </ul>
    </div>
    
    <footer class="article-footer">
       
<div class="share-btn">
      <span class="share-sns share-outer">
        <i class="ri-share-forward-line"></i>
        分享
      </span>
      <div class="share-wrap">
        <i class="arrow"></i>
        <div class="share-icons">
          
          <a class="weibo share-sns" href="javascript:;" data-type="weibo">
            <i class="ri-weibo-fill"></i>
          </a>
          <a class="weixin share-sns wxFab" href="javascript:;" data-type="weixin">
            <i class="ri-wechat-fill"></i>
          </a>
          <a class="qq share-sns" href="javascript:;" data-type="qq">
            <i class="ri-qq-fill"></i>
          </a>
          <a class="douban share-sns" href="javascript:;" data-type="douban">
            <i class="ri-douban-line"></i>
          </a>
          <!-- <a class="qzone share-sns" href="javascript:;" data-type="qzone">
            <i class="icon icon-qzone"></i>
          </a> -->
          
          <a class="facebook share-sns" href="javascript:;" data-type="facebook">
            <i class="ri-facebook-circle-fill"></i>
          </a>
          <a class="twitter share-sns" href="javascript:;" data-type="twitter">
            <i class="ri-twitter-fill"></i>
          </a>
          <a class="google share-sns" href="javascript:;" data-type="google">
            <i class="ri-google-fill"></i>
          </a>
        </div>
      </div>
</div>

<div class="wx-share-modal">
    <a class="modal-close" href="javascript:;"><i class="ri-close-circle-line"></i></a>
    <p>扫一扫，分享到微信</p>
    <div class="wx-qrcode">
      <img src="//api.qrserver.com/v1/create-qr-code/?size=150x150&data=https://blog.shimmerjordan.eu.org/2022/02/25/8SortingAlgorithms/" alt="微信分享二维码">
    </div>
</div>

<div id="share-mask"></div>  
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Algorithm/" rel="tag">Algorithm</a></li></ul>

    </footer>
  </div>

   
  <nav class="article-nav">
    
      <a href="/2022/02/26/topk-algo/" class="article-nav-link">
        <strong class="article-nav-caption">上一篇</strong>
        <div class="article-nav-title">
          
            TopK算法杂记
          
        </div>
      </a>
    
    
      <a href="/2021/11/01/clever-use-of-set/" class="article-nav-link">
        <strong class="article-nav-caption">下一篇</strong>
        <div class="article-nav-title">Clever use of set</div>
      </a>
    
  </nav>

   
<!-- valine评论 -->
<div id="vcomments-box">
  <div id="vcomments"></div>
</div>
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js"></script>
<script>
  new Valine({
    el: "#vcomments",
    app_id: "StYfTMDp78X0EltFR16ve2q5-gzGzoHsz",
    app_key: "G4RPxRpXG6RwdfpnJefOSnyy",
    path: window.location.pathname,
    avatar: "wavatar",
    placeholder: "ヾﾉ≧∀≦)o来啊，快活啊!",
    recordIP: true,
  });
  const infoEle = document.querySelector("#vcomments .info");
  if (infoEle && infoEle.childNodes && infoEle.childNodes.length > 0) {
    infoEle.childNodes.forEach(function (item) {
      item.parentNode.removeChild(item);
    });
  }
</script>
<style>
  #vcomments-box {
    padding: 5px 30px;
  }

  @media screen and (max-width: 800px) {
    #vcomments-box {
      padding: 5px 0px;
    }
  }

  #vcomments-box #vcomments {
    background-color: #fff;
  }

  .v .vlist .vcard .vh {
    padding-right: 20px;
  }

  .v .vlist .vcard {
    padding-left: 10px;
  }
</style>

 
   
   
<!-- minivaline评论 -->
<div id="mvcomments-box">
  <div id="mvcomments"></div>
</div>
<script src="https://cdn.jsdelivr.net/npm/minivaline@latest"></script>
<script>
    new MiniValine(Object.assign({"enable":true,"mode":"DesertsP","placeholder":"Write a Comment","math":true,"md":true,"enableQQ":true,"NoRecordIP":false,"visitor":true,"maxNest":6,"pageSize":6,"adminEmailMd5":"de8a7aa53d07e6b6bceb45c64027763d","tagMeta":["管理员","小伙伴","访客"],"master":["de8a7aa53d07e6b6bceb45c64027763d"],"friends":["b5bd5d836c7a0091aa8473e79ed4c25e","adb7d1cd192658a55c0ad22a3309cecf","3ce1e6c77b4910f1871106cb30dc62b0","cfce8dc43725cc14ffcd9fb4892d5bfc"],"lang":null,"emoticonUrl":["https://cdn.jsdelivr.net/npm/alus@latest","https://cdn.jsdelivr.net/gh/MiniValine/qq@latest","https://cdn.jsdelivr.net/gh/MiniValine/Bilibilis@latest","https://cdn.jsdelivr.net/gh/MiniValine/tieba@latest","https://cdn.jsdelivr.net/gh/MiniValine/twemoji@latest","https://cdn.jsdelivr.net/gh/MiniValine/weibo@latest"]}, {
	  el: '#mvcomments',
    }));
  const infoEle = document.querySelector('#mvcomments .info');
  if (infoEle && infoEle.childNodes && infoEle.childNodes.length > 0) {
      infoEle.childNodes.forEach(function (item) {
          item.parentNode.removeChild(item);
      });
  }
</script>
<style>
	#mvcomments-box {
		padding: 5px 30px;
	}
	@media screen and (max-width: 800px) {
		#mvcomments-box {
		  padding: 5px 0px;
		}
	}
	.darkmode .MiniValine *{
		color: #f1f1f1!important;
	}
	.darkmode .commentTrigger{
		background-color: #403e3e !important;
	  }
	.darkmode .MiniValine .vpage .more{
		background: #21232F
	}
	.darkmode img{
		filter: brightness(30%)
	}
	.darkmode .MiniValine .vlist .vcard .vcomment-body .text-wrapper .vcomment.expand:before{
		background: linear-gradient(180deg, rgba(246,246,246,0), rgba(0,0,0,0.9))
	}
	.darkmode .MiniValine .vlist .vcard .vcomment-body .text-wrapper .vcomment.expand:after{
		background: rgba(0,0,0,0.9)
	}
	.darkmode .MiniValine .vlist .vcard .vcomment-body .text-wrapper .vcomment pre{
		background: #282c34
		border: 1px solid #282c34
	}
	.darkmode .MiniValine .vinputs-area .textarea-wrapper textarea{
		color: #000;
	}
	.darkmode .MiniValine .vinputs-area .auth-section .input-wrapper input{
		color: #000;
	}
	.darkmode .MiniValine .vinputs-area .vextra-area .vsmile-icons{
		background: transparent;
	}
	.darkmode .MiniValine .vinputs-wrap{
		border-color: #b2b2b5;
	}
	.darkmode .MiniValine .vinputs-wrap:hover{
		border: 1px dashed #2196f3;
	}
	.darkmode .MiniValine .vinputs-area .auth-section .input-wrapper{
		border-bottom: 1px dashed #b2b2b5;
	}
	.darkmode .MiniValine .vinputs-area .auth-section .input-wrapper:hover{
		border-bottom: 1px dashed #2196f3;
	}
	.darkmode .MiniValine .vbtn{
		background-color: transparent!important;
	}
	.darkmode .MiniValine .vbtn:hover{
		border: 1px dashed #2196f3;
	}
</style>

    
</article>

</section>
      <footer class="footer">
  <div class="outer">
    <ul>
      <li>
        Copyrights &copy;
        2019-2024
        <i class="ri-heart-fill heart_icon"></i> 鞠桥丹-QIAODAN JU
      </li>
    </ul>
    <ul>
      <li>
        
        
        
        由 <a href="https://hexo.io" target="_blank">Hexo</a> 强力驱动
        <span class="division">|</span>
        主题 - <a href="https://github.com/Shen-Yu/hexo-theme-ayer" target="_blank">Ayer</a>
        
      </li>
    </ul>
    <ul>
      <li>
        
        
        <span>
  <span><i class="ri-user-3-fill"></i>访问人数:<span id="busuanzi_value_site_uv"></span></s>
  <span class="division">|</span>
  <span><i class="ri-eye-fill"></i>浏览次数:<span id="busuanzi_value_page_pv"></span></span>
</span>
        
      </li>
    </ul>
    <ul>
      
    </ul>
    <ul>
      
    </ul>
    <ul>
      <li>
        <!-- cnzz统计 -->
        
        <script type="text/javascript" src='https://s4.cnzz.com/z_stat.php?id=1279035150&amp;web_id=1279035150'></script>
        
      </li>
    </ul>
  </div>
</footer>
      <div class="float_btns">
        <div class="totop" id="totop">
  <i class="ri-arrow-up-line"></i>
</div>

<div class="todark" id="todark">
  <i class="ri-moon-line"></i>
</div>

      </div>
    </main>
    <aside class="sidebar on">
      <button class="navbar-toggle"></button>
<nav class="navbar">
  
  <div class="logo">
    <a href="/"><img src="/images/ayer-side.svg" alt="丛烨-shimmerjordan"></a>
  </div>
  
  <ul class="nav nav-main">
    
    <li class="nav-item">
      <a class="nav-item-link" href="/">Home</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/archives">Catalogue</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags">Tags</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E9%9A%8F%E7%AC%94/">Essay</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/categories">Archives</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/friends">Friends</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/2020/01/18/about">About</a>
    </li>
    
  </ul>
</nav>
<nav class="navbar navbar-bottom">
  <ul class="nav">
    <li class="nav-item">
      
      <a class="nav-item-link nav-item-search"  title="搜索">
        <i class="ri-search-line"></i>
      </a>
      
      
      <a class="nav-item-link" target="_blank" href="/atom.xml" title="RSS Feed">
        <i class="ri-rss-line"></i>
      </a>
      
    </li>
  </ul>
</nav>
<div class="search-form-wrap">
  <div class="local-search local-search-plugin">
  <input type="search" id="local-search-input" class="local-search-input" placeholder="Search...">
  <div id="local-search-result" class="local-search-result"></div>
</div>
</div>
    </aside>
    <script>
      if (window.matchMedia("(max-width: 768px)").matches) {
        document.querySelector('.content').classList.remove('on');
        document.querySelector('.sidebar').classList.remove('on');
      }
    </script>
    <div id="mask"></div>

<!-- #reward -->
<div id="reward">
  <span class="close"><i class="ri-close-line"></i></span>
  <p class="reward-p"><i class="ri-cup-line"></i>请我喝杯蓝莓汁吧~</p>
  <div class="reward-box">
    
    <div class="reward-item">
      <img class="reward-img" src="/images/alipay.jpg">
      <span class="reward-type">支付宝</span>
    </div>
    
    
    <div class="reward-item">
      <img class="reward-img" src="/images/wechat.jpg">
      <span class="reward-type">微信</span>
    </div>
    
  </div>
</div>
    
<script src="/js/jquery-2.0.3.min.js"></script>


<script src="/js/lazyload.min.js"></script>

<!-- Tocbot -->


<script src="/js/tocbot.min.js"></script>

<script>
  tocbot.init({
    tocSelector: '.tocbot',
    contentSelector: '.article-entry',
    headingSelector: 'h1, h2, h3, h4, h5, h6',
    hasInnerContainers: true,
    scrollSmooth: true,
    scrollContainer: 'main',
    positionFixedSelector: '.tocbot',
    positionFixedClass: 'is-position-fixed',
    fixedSidebarOffset: 'auto'
  });
</script>

<script src="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.js"></script>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.css">
<script src="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/js/jquery.justifiedGallery.min.js"></script>

<script src="/dist/main.js"></script>

<!-- ImageViewer -->

<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>

    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">

        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                <!--  Controls are self-explanatory. Order can be changed. -->

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" style="display:none" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.min.css">
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"></script>

<script>
    function viewer_init() {
        let pswpElement = document.querySelectorAll('.pswp')[0];
        let $imgArr = document.querySelectorAll(('.article-entry img:not(.reward-img)'))

        $imgArr.forEach(($em, i) => {
            $em.onclick = () => {
                // slider展开状态
                // todo: 这样不好，后面改成状态
                if (document.querySelector('.left-col.show')) return
                let items = []
                $imgArr.forEach(($em2, i2) => {
                    let img = $em2.getAttribute('data-idx', i2)
                    let src = $em2.getAttribute('data-target') || $em2.getAttribute('src')
                    let title = $em2.getAttribute('alt')
                    // 获得原图尺寸
                    const image = new Image()
                    image.src = src
                    items.push({
                        src: src,
                        w: image.width || $em2.width,
                        h: image.height || $em2.height,
                        title: title
                    })
                })
                var gallery = new PhotoSwipe(pswpElement, PhotoSwipeUI_Default, items, {
                    index: parseInt(i)
                });
                gallery.init()
            }
        })
    }
    viewer_init()
</script>

<!-- MathJax -->

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
      tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
  });

  MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
      for(i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
      }
  });
</script>

<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.6/unpacked/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
  var ayerConfig = {
    mathjax: true
  }
</script>

<!-- Katex -->

<!-- busuanzi  -->


<script src="/js/busuanzi-2.3.pure.min.js"></script>


<!-- ClickLove -->


<script src="/js/clickLove.js"></script>


<!-- ClickBoom1 -->

<!-- ClickBoom2 -->

<!-- CodeCopy -->


<link rel="stylesheet" href="/css/clipboard.css">

<script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script>
  function wait(callback, seconds) {
    var timelag = null;
    timelag = window.setTimeout(callback, seconds);
  }
  !function (e, t, a) {
    var initCopyCode = function(){
      var copyHtml = '';
      copyHtml += '<button class="btn-copy" data-clipboard-snippet="">';
      copyHtml += '<i class="ri-file-copy-2-line"></i><span>COPY</span>';
      copyHtml += '</button>';
      $(".highlight .code pre").before(copyHtml);
      $(".article pre code").before(copyHtml);
      var clipboard = new ClipboardJS('.btn-copy', {
        target: function(trigger) {
          return trigger.nextElementSibling;
        }
      });
      clipboard.on('success', function(e) {
        let $btn = $(e.trigger);
        $btn.addClass('copied');
        let $icon = $($btn.find('i'));
        $icon.removeClass('ri-file-copy-2-line');
        $icon.addClass('ri-checkbox-circle-line');
        let $span = $($btn.find('span'));
        $span[0].innerText = 'COPIED';
        
        wait(function () { // 等待两秒钟后恢复
          $icon.removeClass('ri-checkbox-circle-line');
          $icon.addClass('ri-file-copy-2-line');
          $span[0].innerText = 'COPY';
        }, 2000);
      });
      clipboard.on('error', function(e) {
        e.clearSelection();
        let $btn = $(e.trigger);
        $btn.addClass('copy-failed');
        let $icon = $($btn.find('i'));
        $icon.removeClass('ri-file-copy-2-line');
        $icon.addClass('ri-time-line');
        let $span = $($btn.find('span'));
        $span[0].innerText = 'COPY FAILED';
        
        wait(function () { // 等待两秒钟后恢复
          $icon.removeClass('ri-time-line');
          $icon.addClass('ri-file-copy-2-line');
          $span[0].innerText = 'COPY';
        }, 2000);
      });
    }
    initCopyCode();
  }(window, document);
</script>


<!-- CanvasBackground -->


<script src="/js/dz.js"></script>



    
  </div>
</body>

</html>